翻訳と辞書 Words near each other ・ Graphic design occupations ・ Graphic designer ・ Graphic Era Hill University ・ Graphic Era University ・ Graphic Exchange Magazine ・ Graphic facilitation ・ Graphic Imaging Technology ・ Graphic kit ・ Graphic matroid ・ Graph (mathematics) ・ Graph algebra ・ Graph algebra (social sciences) ・ GRAph ALigner (GRAAL) ・ Graph amalgamation ・ Graph automorphism ・ Graph bandwidth ・ Graph C*-algebra ・ Graph canonization ・ Graph center ・ Graph coloring ・ Graph coloring game ・ Graph continuous function ・ Graph cut ・ Graph cuts in computer vision ・ Graph database ・ Graph drawing ・ Graph dynamical system ・ Graph embedding ・ Graph energy ・ Graph enumeration Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Graph bandwidth ： ウィキペディア英語版 Graph bandwidth In graph theory, the graph bandwidth problem is to label the ''n'' vertices ''vi'' of a graph ''G'' with distinct integers ''f''(''vi'') so that the quantity $\backslash max\backslash$ is minimized (''E'' is the edge set of ''G''). The problem may be visualized as placing the vertices of a graph at distinct integer points along the ''x''-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.〔 The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights ''wij'' and the cost function to be minimized is $\backslash max\backslash$. In terms of matrices, the (unweighted) graph bandwidth is the bandwidth of the symmetric matrix which is the adjacency matrix of the graph. The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size . ==Bandwidth formulas for some graphs== For several families of graphs, the bandwidth $\backslash varphi(G)$ is given by an explicit formula. The bandwidth of a path graph ''P''''n'' on ''n'' vertices is 1, and for a complete graph ''K''''m'' we have $\backslash varphi(K\_n)=n-1$. For the complete bipartite graph ''K''''m'',''n'', :$\backslash varphi(K\_)\; =\; \backslash lfloor\; (m-1)/2\backslash rfloor+n$, assuming $m\; \backslash ge\; n\backslash ge\; 1,$ which was proved by Chvátal.〔A remark on a problem of Harary. V. Chvátal, ''Czechoslovak Mathematical Journal'' 20(1):109–111, 1970. (http://dml.cz/dmlcz/100949 )〕 As a special case of this formula, the star graph $S\_k\; =\; K\_$ on ''k'' + 1 vertices has bandwidth $\backslash varphi(S\_)\; =\; \backslash lfloor\; (k-1)/2\backslash rfloor+1$. For the hypercube graph $Q\_n$ on $2^n$ vertices the bandwidth was determined by to be :$\backslash varphi(Q\_n)=\backslash sum\_^\; \backslash binom.$ Chvatálová showed〔Optimal Labelling of a product of two paths. J. Chvatálová, ''Discrete Mathematics'' 11, 249–253, 1975.〕 that the bandwidth of the ''m'' × ''n'' square grid graph $P\_m\; \backslash times\; P\_n$, that is, the Cartesian product of two path graphs on $m$ and $n$ vertices, is equal to min. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph bandwidth」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.